/*
 * Alvin Baldemeca
 * HW2Prob4.java
 * 4/15/2014
 * UWT TCSS343B
 * Prof. Ling Ding
 * 
 */


import static java.lang.Math.abs;
import java.util.HashMap;

/**
 * 
 * @author Alvin Baldemeca
 * This class crates a number of points and calls the method maxNumPoints() to calculate
 * the maximum number of points in a line from the set of points provided.
 * 
 * How it works:
 * 
 * maxNumPoints() is a brute force algorithm with an asymptotic runtime of 0(n^2).
 * Given a set of points we choose the first point and compute the slope from this point
 * to a different point in the set, we do this for all the points in the set.  Then we 
 * choose the next point and compute the slope for all the point in the set.  A hash map
 * is used to keep track of equivalent slope because points that have equivalent slopes
 * lies on the same line.  We check and keep the largest value we come across, which is the
 * maximum number of points that form a line in a given set.  
 *
 */
public class HW2Prob4 {

	
	/**
	 * Caculates the maximum number of points on the same line for a given set of points.
	 * @param inputs - the set of points i.e. Point[]
	 * @return - the maximum number of points on the same line for a given set of points.
	 */
    public int maxNumPoints(Point[] inputs){

    	//Place holder for the maximum number of points that form a line.
        int max = 0;
        
        //We iterate through all the points making it the reference to calculate the
        //slope
        for(int i = 0; i < inputs.length; i++)
        {
                //This hashmap keeps the unique slope count for the given reference 
        	    //point.  
                HashMap<Float, Integer> slopeMap = new HashMap<Float, Integer>();
                
                //Used to store the number of points in a no slope line
                int nSlope = 1;
                
                //The slope of the reference point and another point is stored here.
                float slopeKey = 0;
                
                //The count of repeating slope, its initialize to 1 because 2 points
                //are needed to compute the slope.
                int repeat = 1;
                
                //Calculate slope for the point and all other points
                for(int j = 0; j < inputs.length; j++)
                {
                	    //If the reference point is the same as the current point 
                	    //skip calculating the slope.
                        if(i==j)
                        {
                                continue;
                        }else{
                                //If we have a no slope count this point on the no slope line
                                if(inputs[i].x == inputs[j].x)
                                {
                                        nSlope++;

                                }else{
                                	//Calculate the slope of the reference point and the other point
                                	slopeKey = (float) (abs(inputs[j].y - inputs[i].y + 0.00) / abs(inputs[j].x - inputs[i].x + 0.00));
                                    
                                	//If the slope is not unique add 1 to the number of points that have this slope
                                	if(slopeMap.containsKey(slopeKey)){
                                		int temp = slopeMap.get(slopeKey);
                                		++temp;
                                		slopeMap.put(slopeKey, temp);
               
                                	} else{//If this is a unique slope we add this to the hash map with a value of 2 points
                                		slopeMap.put(slopeKey, 2);
                                	}
                                }
                                    
                            }

                    }
                
                    //Select the slope with the most points
                    for (int value : slopeMap.values()) {
                	
	                	if(value > repeat)
	                	{
	                		repeat = value;
	                	}
                    
                     }
             
            //Update max if the no slope line is greater or the points of a particular slope is grater        
            if(max < nSlope && repeat <= nSlope)
            {
                    max = nSlope;
            }else if(max < repeat)
            {
                    max = repeat;
            }
        }

        return max;
    }

 


public static void main(String[] arg){
	
                Point p0 = new Point(12,-22);
                Point p1 = new Point(1,1);
                Point p2 = new Point(1,2);
                Point p3 = new Point(1,3);
                Point p4 = new Point(2,12);
                Point p5 = new Point(3,12);
                Point p6 = new Point(4,12);
                Point p7 = new Point(2,9);
                Point p8 = new Point(4,16);
                Point p9 = new Point(6,23);
                Point p10 = new Point(8,30);
                Point p11 = new Point(10,37);
                Point p12 = new Point(12,44);
                Point p13 = new Point(14,51);
                Point p14 = new Point(-12,13);
                Point p15 = new Point(-4,8);
                Point p16 = new Point(15,10);
                Point p17 = new Point(13,57);
                Point p18 = new Point(34,81);
                Point p19 = new Point(76,75);
                Point p20 = new Point(1,52);

                Point[] pointArray = new Point[] { p0, p1, p2, p3, p4, p5, p6, p7, p8, p9, p10,
                                p11, p12, p13, p14, p15, p16, p17, p18, p19, p20
                };

                HW2Prob4 prob = new HW2Prob4();
                int num_of_points = prob.maxNumPoints(pointArray);

                System.out.println("The max number of points lying in the same line is "
                + num_of_points);

        }

}
